package leetCode.hw.dp;

public class HJ75Solution implements HJ75{


    /**
     * 递归解法, 无效计算过多,容易超时
     * @param str1
     * @param str2
     * @return
     */
    @Override
    public int getMaxSubStrLength(String str1, String str2) {
        int result  = 0;
        if(str2.contains(str1)) {
            result = str1.length();
        }
        else {
            result = Math.max(getMaxSubStrLength(str1.substring(1),str2),getMaxSubStrLength(str1.substring(0,str1.length()-1),str2));
        }
        return result;
    }

    /**
     * 动态规划法
     * @param str1
     * @param str2
     * @return
     */
    public int getMaxSubStrLength3(String str1,String str2) {
        int result = 0;
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        for(int i=0;i<str1.length();i++) {
            for(int j=0;j<str2.length();j++) {
                if(str1.charAt(i)==str2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j]+1;
                }
                if(dp[i+1][j+1]>result) result = dp[i+1][j+1];
            }
        }
        return result;
    }

    /**
     * 动态规划解法(迭代法)
     * @param str1
     * @param str2
     * @return
     */
    public int getMaxSubStrLength2(String str1,String str2) {
        int result = 0;
        int i = 0, j = str1.length();
        while (i<j) {
            int res = subQuest(str1.substring(i,j),str2);
            if(result < res) {
                result = res;
            }
            i++;
            j--;
        }
        return result;
    }

    /**
     * 子问题解法
     * @param str1
     * @param str2
     * @return
     */
    public static int subQuest(String str1, String str2) {
        int result  = 0;
        for (int i = 0; i < str1.length(); i++) {
            String sub = str1.substring(i);
            if (str2.contains(sub)) {
                if (result < sub.length()) {
                    result = sub.length();
                }
            }
        }
        for (int i = str1.length(); i >= 0; i--) {
            String sub = str1.substring(0, i);
            if (str2.contains(sub)) {
                if (result < sub.length()) {
                    result = sub.length();
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 答案是4
        //System.out.println(new HJ75Solution().getMaxSubStrLength("dedcecfbbbecaffedcedbadadbbfaafcafdd","bacefaebcdfabfaadebdaacabbdabcfffbdcebaabecefddfaceeebaeabebbad"));
        System.out.println(new HJ75Solution().getMaxSubStrLength2("dedcecfbbbecaffedcedbadadbbfaafcafdd","bacefaebcdfabfaadebdaacabbdabcfffbdcebaabecefddfaceeebaeabebbad"));
    }

}
